package labuladong.leetcode.editor.cn._01linkedlist.ch01;

public class _206_ReverseLinkedList {

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        // 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
        public ListNode reverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode last = reverseList(head.next);
            head.next.next = head;
            head.next = null;
            return last;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    // 创建链表
    private static ListNode build(int[] nums) {
        ListNode dummy = new ListNode(-1), p = dummy;

        for (int num : nums) {
            p.next = new ListNode(num);
            p = p.next;
        }
        return dummy.next;
    }

    // 打印链表
    private static void print(ListNode node) {
        while (node != null) {
            if (node.next == null) {  //链表最后一个节点
                System.out.print(node.val);
                break;
            }
            System.out.print(node.val + "->");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Solution solution = new _206_ReverseLinkedList().new Solution();

        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = build(nums);
        print(head);

        ListNode res = solution.reverseList(head);
        print(res);
    }
}
